package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

// https://blog.csdn.net/qq_41953962/article/details/107312598
public class Code22_PathWithMaximumProbability {

	public static double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
		List<List<Pair>> graph = new ArrayList<List<Pair>>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<Pair>());
		}
		for (int i = 0; i < edges.length; i++) {
			int[] e = edges[i];
			graph.get(e[0]).add(new Pair(succProb[i], e[1]));
			graph.get(e[1]).add(new Pair(succProb[i], e[0]));
		}

		PriorityQueue<Pair> que = new PriorityQueue<Pair>();
		double[] prob = new double[n];

		que.offer(new Pair(1, start));
		prob[start] = 1;
		while (!que.isEmpty()) {
			Pair pair = que.poll();
			double pr = pair.probability;
			int node = pair.node;
			if (pr < prob[node]) {
				continue;
			}
			for (Pair pairNext : graph.get(node)) {
				double prNext = pairNext.probability;
				int nodeNext = pairNext.node;
				if (prob[nodeNext] < prob[node] * prNext) {
					prob[nodeNext] = prob[node] * prNext;
					que.offer(new Pair(prob[nodeNext], nodeNext));
				}
			}
		}
		return prob[end];
	}

	public static class Pair implements Comparable<Pair> {
		double probability;
		int node;

		public Pair(double probability, int node) {
			this.probability = probability;
			this.node = node;
		}

		public int compareTo(Pair pair2) {
			if (this.probability == pair2.probability) {
				return this.node - pair2.node;
			} else {
				return this.probability - pair2.probability > 0 ? -1 : 1;
			}
		}
	}

//	  public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
//	    	//通过邻接表构建图，注意创建泛型数组时候的处理
//	        LinkedList<double[]>[] graph = new LinkedList[n];
//	        for (int i = 0; i < n; i++) {
//	            graph[i] = new LinkedList<>();
//	        }
//	        //加入每个节点的邻居元素 这里采用数组[节点，概率]来表示
//	        for (int i = 0; i < edges.length; i++) {
//	            graph[edges[i][0]].add(new double[] { edges[i][1], succProb[i] });
//	            graph[edges[i][1]].add(new double[] { edges[i][0], succProb[i] });
//	        }
//
//	        //Dijkstra算法
//	        //PriorityQueue用于储存当前被发现的结点以及相应的概率
//	        //通过每次的迭代,概率最大的结点将被取出并且访问，所以采用一个大顶堆，通过lambda实现
//	        PriorityQueue<double[]> queue = new PriorityQueue<>((a, b) -> Double.compare(b[1], a[1]));
//	        //用于判断结点是否被访问过了，可以在后面有效防止无意义的回溯
//	        boolean[] visited = new boolean[n];
//	        queue.add(new double[] { start, 1 });
//	        while (!queue.isEmpty()) {
//	        	//弹出当前概率最大的路径顶点元素
//	            double[] cur = queue.remove();
//	            if (cur[0] == end) {
//	                return cur[1];
//	            } else if (!visited[(int) cur[0]]) {
//	                visited[(int) cur[0]] = true;
//	                for (double[] next : graph[(int) cur[0]]) {
//	                	//这里没有选择去重，其实去重的话可以再优化下一些些空间复杂度
//	                    if (!visited[(int) next[0]]) {
//	                        queue.add(new double[] { next[0], head[1] * next[1] });
//	                    }
//	                }
//	            }
//	        }
//	        //如果与起始节点相连通的结点都被访问后还没找到最终结点，说明并不联通，概率为0
//	        return 0;
//	    }
//	

	public static void main(String[] args) {
		{
			int n = 3;
			int[][] edges = new int[][] { { 0, 1 }, { 1, 2 }, { 0, 2 } };
			double[] succProb = new double[] { 0.5, 0.5, 0.2 };
			int start = 0;
			int end = 2;

			System.out.println(maxProbability(n, edges, succProb, start, end));
		}
	}
}
